XFastTrie: Searching in doubly-logarithmic Time#

The performance of the BinaryTrie structure is not very impressive. The number of elements, n, stored in the structure is at most 2w2^w, so lognw\log n \leq w. In other words, any of the comparison-based SSet are at least as efficient as a BinaryTrie, and are not restricted to only storing integers.

Next we describe the XFastTrie, which is just a BinaryTrie with w+1w + 1 hash tables—one for each level of the trie. These hash tables are used to speed up the find(x) operation to O(logw)O(\log w) time. Recall that the find(x) operation in a BinaryTrie is almost complete once we reach a node, u, where the search path for x would like to proceed to u.right (or u.left) but u has no right (respectively, left) child. At this point, the search uses u.jump to jump to a leaf, v, of the BinaryTrie and either return v or its successor in the linked list of leaves. An XFastTrie speeds up the search process by using binary search on the levels of the trie to locate the node u.

To use binary search, we need a way to determine if the node u we are looking for is above a particular level, i, of if u is at or below level i. This information is given by the highest-order i bits in the binary representation of x; these bits determine the search path that x takes from the root to level i.

Visual demonstration of the search path#

The visual demonstration of the search path is shown below:

Created with Fabric.js 3.6.6

1 of 3

Created with Fabric.js 3.6.6

2 of 3

Created with Fabric.js 3.6.6

3 of 3

For an example, in the above illustration; the last node, u, on search path for 1414 (whose binary representation is 11101110) is the node labelled 1111\star \star at level 22 because there is no node labelled 111111\star at level 33. Thus, we can label each node at level ii with an ii-bit integer.

Then, the node u we are searching for would be at or below level i if and only if there is a node at level i whose label matches the highest-order i bits of x.

In an XFastTrie, we store, for each i{0,...,w}i \in \{0,...,w\}, all the nodes at level i in a USet, t[i], that is implemented as a hash table. Using this USet allows us to check in constant expected time if there is a node at level i whose label matches the highest-order i bits of x. In fact, we can even find this node using t[i].find (x>>>(w − i)).

The hash tables t[0],...,t[w]t[0],...,t[w] allow us to use binary search to find u. Initially, we know that u is at some level i with 0i<w+10 \leq i < w+1. We therefore initialize l = 0 and h = w + 1 and repeatedly look at the hash table t[i], where i=(l+h)/2i = \left \lfloor (l + h)/2\right \rfloor. If t[i]t[i] contains a node whose label matches xx’s highest-order ii bits then we set l = i (u is at or below level i); otherwise we set h = i (u is above level i). This process terminates when hl1h − l \leq 1, in which case we determine that u is at level l. We then complete the find(x) operation using u.jump and the doubly-linked list of leaves.

The find() method

Each iteration of the while loop in the above method decreases h − l by roughly a factor of two, so this loop finds u after O(logw)O(\log w) iterations. Each iteration performs a constant amount of work and one find(x) operation in a USet, which takes a constant expected amount of time. The remaining work takes only constant time, so the find(x) method in an XFastTrie takes only O(logw)O(\log w) expected time.

The add(x) and remove(x) methods for an XFastTrie are almost identical to the same methods in a BinaryTrie. The only modifications are for managing the hash tables t[0],...,t[w]t[0],. . . ,t[w]. During the add(x) operation, when a new node is created at level i, this node is added to t[i]. During a remove(x) operation, when a node is removed form level i, this node is removed from t[i]. Since adding and removing from a hash table take constant expected time, this does not increase the running times of add(x) and remove(x) by more than a constant factor. We omit a code listing for add(x) and remove(x) since the code is almost identical to the (long) code listing already provided for the same methods in a BinaryTrie.

The following theorem summarizes the performance of an XFastTrie:

Theorem 1: An XFastTrie implements the SSet interface for ww-bit integers. An XFastTrie supports the operations

  • add(x) and remove(x) in O(w)O(w) expected time per operation and
  • find(x) in O(logw)O(\log w) expected time per operation.

The space used by an XFastTrie that stores n values is O(nw)O(n \cdot w).

Let’s now create an instance of XFastTrie class and adds and remove values using the add() and remove() methods.

main.py
linearhashtable.py
binarytrie.py
base.py
utils.py
Implementation of XFastTrie

Explanation

Let’s start our explanation from the start of main() in the main.py file.

  • Line 126: It creates an instance of XFastTrie(), xfast_trie.
  • Line 128–133: It adds value to the xfast_trie using the add() method.
  • Line 138–140: It finds value to the xfast_trie using the find() method. It will return the value if it’s present in the xfast_trie.
  • Line 142–144: It removes the values from the xfast_trie using the remove() method and update the xfast_trie.
  • Line 149–151: It searches for the values in xfast_trie using the find() method and returns the value if it is present.

YFastTrie: a doubly-logarithmic time SSet#

The XFastTrie is a vast—even exponential—improvement over the BinaryTrie in terms of query time, but the add(x) and remove(x) operations are still not terribly fast. Furthermore, the space usage, O(nw)O(n \cdot w), is higher than the other SSet implementations, which all use O(n)O(n) space. These two problems are related; if nn add(x) operations build a structure of size nwn · w, then the add(x) operation requires at least on the order of ww time (and space) per operation.

The YFastTrie, discussed next, simultaneously improves the space and speed of XFastTries. A YFastTrie uses an XFastTrie, xft, but only stores O(n/w)O(n/w) values in xft. In this way, the total space used by xft is only O(n)O(n). Furthermore, only one out of every ww add(x) or remove(x) operations in the YFastTrie results in an add(x) or remove(x) operation in xft. By doing this, the average cost incurred by calls to xft’s add(x) and remove(x) operations is only constant.

The obvious question becomes: If xft only stores n/wn/w elements, where do the remaining n(11/w)n(1 − 1/w) elements go? These elements move into secondary structures, in this case an extended version of treaps. There are roughly n/wn/w of these secondary structures so, on average, each of them stores O(w)O(w) items. Treaps support logarithmic time SSet operations, so the operations on these treaps will run in O(logw)O(\log w) time, as required.

More concretely, a YFastTrie contains an XFastTrie, xft, that contains a random sample of the data, where each element appears in the sample independently with probability 1/w1/w. For convenience, the value 2w12^w − 1, is always contained in xft. Let x0<x1<<xk1x_0 < x_1 < ··· < x_{k−1} denote the elements stored in xft. Associated with each element, xix_i, is a treap, tit_i, that stores all values in the range xi1+1,...,xix_{i−1} + 1,...,x_i.

Visual demonstration ofYFastTrie#

This is illustrated below:

 A YFastTrie containing the values 0, 1, 3, 4, 6, 8, 9, 10, 11, and 13
A YFastTrie containing the values 0, 1, 3, 4, 6, 8, 9, 10, 11, and 13

The find(x) operation in a YFastTrie is fairly easy. We search for x in xft and find some value xi associated with the treap tit_i. We then use the treap find(x) method on tit_i to answer the query. The entire method is a one-liner:

The find() method

The first find(x) operation (on xft) takes O(logw)O(\log w) time. The second find(x) operation (on a treap) takes O(logr)O(\log r) time, where r is the size of the treap. Later in this section, we will show that the expected size of the treap is O(w)O(w) so that this operation takes O(logw)O(\log w) time. This is an application of Jensen’s Inequality: If E[r]=wE[r] = w, then E[logr]logwE[\log r] \leq \log w.

Adding an element to a YFastTrie is also fairly simple—most of the time. The add(x) method calls xft.find(x) to locate the treap, tt, into which x should be inserted. It then calls t.add(x) to add x to t. At this point, it tosses a biased coin that comes up as heads with probability 1/w1/w and as tails with probability 11/w1 − 1/w. If this coin comes up heads, then x will be added to xft.

This is where things get a little more complicated. When x is added to xft, the treap t needs to be split into two treaps, t1t1 and tt^{\prime}. The treap t1t1 contains all the values less than or equal to x; tt^{\prime} is the original treap, t, with the elements of t1t1 removed. Once this is done, we add the pair (x, t1) to xft. The following illustration shows an example.

 Adding the values 2 and 6 to a YFastTrie. The coin toss for 6 came up heads, so 6 was added to xft and the treap containing 4,5,6,8,9 was split
Adding the values 2 and 6 to a YFastTrie. The coin toss for 6 came up heads, so 6 was added to xft and the treap containing 4,5,6,8,9 was split

The implementation of the add() method is:

The add() method

Adding x to t takes O(logw)O(\log w) time. Splitting tt into t1t1 and tt^{\prime} can also be done in O(logw)O(\log w) expected time. Adding the pair (x, t1) to xft takes O(w)O(w) time, but only happens with probability 1/w1/w. Therefore, the expected running time of the add(x) operation is

O(logw)+1wO(w)=O(logw)O(\log w) + \frac{1}{w} O(w) = O(\log w)

The remove(x) method undoes the work performed by add(x). We use xft to find the leaf, u, in xft that contains the answer to xft.find(x). From u, we get the treap, t, containing x and remove x from t. If x was also stored in xft (and x is not equal to 2w12^w−1) then we remove x from xft and add the elements from xx’s treap to the treap, t2t2, that is stored by uu’s successor in the linked list. This is illustrated below.

Removing the values 1 and 9 from a YFastTrie
Removing the values 1 and 9 from a YFastTrie

The implementation of the remove() method is:

The remove() method

Finding the node u in xft takes O(logw)O(\log w) expected time. Removing x from t takes O(logw)O(\log w) expected time. Merging all the elements of tt into t2t2 can be done in O(logw)O(\log w) time. If necessary, removing x from xft takes O(w)O(w) time, but x is only contained in xft with probability 1/w1/w. Therefore, the expected time to remove an element from a YFastTrie is O(logw)O(\log w).

Earlier in the discussion, we delayed arguing about the sizes of treaps in this structure until later. Before finishing this module, we prove the result we need.

Lemma 1. Let x be an integer stored in a YFastTrie and let nxn_x denote the number of elements in the treap, t, that contains x. Then E[nx]2w1E[n_x] \leq 2w − 1.

 The number of elements in the treap t containing x is determined by two coin tossing experiment
The number of elements in the treap t containing x is determined by two coin tossing experiment

Proof: Refer to above illustration. Let x1<x2<<xi=x<xi+1<<xnx_1 < x_2 < ··· < x_i = x < x_{i+1} < ··· < x_n denote the elements stored in the YFastTrie. The treap t contains some elements greater than or equal to x. These are xi,xi+1,...,xi+j1x_i ,x_{i+1},...,x_{i+j−1}, where xi+j1x_{i+j−1} is the only one of these elements in which the biased coin toss performed in the add(x) method turned up as heads. In other words, E[j]E[j] is equal to the expected number of biased coin tosses required to obtain the first heads.

Note: This analysis ignores the fact that jj never exceeds ni+1n−i + 1. However, this only decreases E[j]E[j], so the upper bound still holds.

Similarly, the elements of t smaller than x are xi1,...,xikx_{i−1},...,x_{i−k} where all these kk coin tosses turn up as tails and the coin toss for xik1x_{i−k−1} turns up as heads. Therefore, E[k]w1E[k] \leq w − 1, since this is the same coin tossing experiment considered in the preceding paragraph, but one in which the last toss is not counted. In summary, nx=j+kn_x = j + k, so

E[nx]=E[j+k]=E[j]+E[k]2w1E[n_x] = E[j + k] = E[j] + E[k] \leq 2w − 1

Lemma 1 was the last piece in the proof of the following theorem, which summarizes the performance of the YFastTrie:

Theorem 2: A YFastTrie implements the SSet interface for w-bit integers. A YFastTrie supports the operations add(x), remove(x), and find(x) in O(logw)O(\log w) expected time per operation. The space used by a YFastTrie that stores n values is O(n+w)O(n + w).

The ww term in the space requirement comes from the fact that xft always stores the value 2w12^w − 1. The implementation could be modified (at the expense of adding some extra cases to the code) so that it is unnecessary to store this value. In this case, the space requirement in the theorem becomes O(n)O(n).

Let’s now create an instance of YFastTrie class and use it by adding, searching, and removing elements in a random manner.

main.py
arrayqueue.py
binarytree.py
binarysearchtree.py
linearhashtable.py
binarytrie.py
xfasttrie.py
treap.py
utils.py
base.py
Implementation of YFastTrie

Explanation

Let’s start our explanation from the start of main():

  • Line 109: Initializing a new Random object with a seed value of 0.
  • Line 111–114: Adding n random integers to the YFastTrie, using the randInt method of the Random object to generate values between 0 and 100 times n.
  • Line 117–118: Printing the values of the xft list, which contains the minimum values of each block in the YFastTrie.
  • Line 120–121: Printing the values of the xft list, which contains the maximum values of each block in the YFastTrie.
  • Line 125–127: Searching for n random integers in the YFastTrie, using the find() method to check if each value is in the tree.

Partial Integers

Quiz on Data Structures for Integers